Exercises for Local Search for
n
-Queens Problem
Board size:
Maximum number of trials:
Let's start the exercise by reading the above inputs.
<div id='tr1-output'></div> <script> var SIZE; var MAX; // read the board size, and the maximum number of trials SIZE = document.getElementById("size").value; MAX = document.getElementById("max-trials").value; // column variables var columns = []; // Each column variable keeps the position of a queen which lies in [0, MAX). for (var col = 0; col < SIZE; col++) columns[col] = -1; document.getElementById("tr1-output").innerHTML = "SIZE = " + SIZE + ", MAX = " + MAX; </script>
Execute the code
Exercise 2 - Initialize the board
: This exercise should be done after the above Exercise.
<div id='tr2-output'></div> <script> function initialize(columns) { for (var col = 0; col < columns.length; col++) columns[col] = ???; // Math.floor(), Math.random() } initialize(columns); $('#tr2-output').html(columns[0] + ", " + columns[1] + ", " + columns[2] + ", " + columns[3] + ", " + columns[4]); </script>
Execute the code
Exercise 3 - Count the number of conflicts with the queen in the specified column
: This exercise should be done after Exercise 2.
<div id='tr3-output'></div> <script> function countConflicts(columns, col) { var count = 0; // the same row for (var c = 0; c < columns.length; c++) ??? // the positive diagonal for (var c = 0; c < columns.length; c++) if (c < col) { if (columns[c] == columns[col] - (col - c)) count++; } else if (c > col) { ??? } // the negative diagonal ??? return count; } $('#tr3-output').html(countConflicts(columns, 0) + ", " + countConflicts(columns, 1) + ", " + countConflicts(columns, 2) + ", " + countConflicts(columns, 3) + ", " + countConflicts(columns, 4)); </script>
Execute the code
Exercise 4 - Goal test
: This exercise should be done after Exercise 3.
<div id='tr4-output'></div> <script> function isGoal(columns) // It needs to return true or false. { ??? } var test_result = isGoal(columns); $('#tr4-output').html("" + test_result); </script>
Execute the code
Exercise 5 - Improve the board over the specified column
: This exercise should be done after Exercise 4.
<div id='tr5-output'></div> <script> function improve(columns, col) { var currentPosition = columns[col]; var currentConflicts = countConflicts(columns, col); var minPosition = currentPosition; var minConflicts = currentConflicts; // find the position that has minimum conflicts ??? // if better position is found, // update the position, and // return true. ??? // recover the current positon columns[col] = currentPosition; return false; } $('#tr5-output').html(improve(columns, 0) + ", " + improve(columns, 1) + "<br>" + columns[0] + ", " + columns[1] + ", " + columns[2] + ", " + columns[3] + ", " + columns[4]); </script>
Execute the code
Exercise 6 - Local search
: This exercise should be done after Exercise 5.
<div id='tr6-output'></div> <script> $('#tr6-output').html(columns[0] + ", " + columns[1] + ", " + columns[2] + ", " + columns[3] + ", " + columns[4]); function localSearch(columns) { var improved; while(???) { // until there is no improvement // improve for each column ??? // if there is no more improvement, then break ??? } } localSearch(columns); $('#tr6-output').html($('#tr6-output').html() + "<br>" + columns[0] + ", " + columns[1] + ", " + columns[2] + ", " + columns[3] + ", " + columns[4]); </script>
Execute the code